package com.dragon.datastructure.linkedlist;

/**
 * 查找单链表中的倒数第k个结点【新浪面试题】
 *
 * @author dragon
 * @since 2019/12/17
 */
public class Test2 {

    private static class Node {
        Node next;
        int val;
    }

    /**
     * 查找倒数第lastIndex个节点
     *
     * @param head      头节点
     * @param lastIndex 倒数第lastIndex个
     * @return 查找到的节点
     */
    public static Node findLastIndexNode(Node head, int lastIndex) {
        if (head == null) {
            return null;
        }
        int size = 0;
        Node cur = head;
        while (cur != null) {
            ++size;
            cur = cur.next;
        }
        if (lastIndex <= 0 || lastIndex > size) {
            return null;
        }
        int index = size - lastIndex;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        return cur;
    }
}

